Ensuring the integrity and authenticity of data is of ever increasing importance as data are generated by multiple sources, often outside the direct control of fully trusted entities. Increasingly, data are subjected to environments which can result in invalid (malicious or inadvertent) modifications to the data. Such possibilities clearly arise when data are hosted in a cloud computing environment where complete control over the hardware and software running at the cloud servers is lacking. Invalid modifications can also arise when the data are maintained on trusted servers, but the data may get modified by a malicious insider or an intruder that manages to compromise the server or the communication channels. In these situations, it is desirous to be ensured that the data retrieved from an untrusted server are trustworthy (i.e., the data and retrieved values have not been tampered or incorrectly modified).
With the advent of Cloud Computing there is increasing interest to move operations, including databases, onto a cloud platform. Although Cloud Computing holds great promise, it raises a number of security and privacy concerns. It also raises concerns about the fidelity of the service. In particular, since the clients have little or no direct control over the software and hardware that is running at the servers, there is reluctance to blindly trust the server. For example, a server may be improperly configured, or inadvertently left open to hacker attacks. There is also the concern about the server being attacked by an external entity that can corrupt the outsourced data or service despite the best efforts of the server. Even though, the cloud service provider is likely to be honest, it may try to hide its failure. Currently, users have no recourse but to trust the server or rely on legal agreements. Even with such agreements, it is difficult for a user to discover, let alone prove, any foul play by the server.
For purposes of this application, the term “untrusted database” is used herein to refer to one or more of the of the following situations: (1) a database that is hosted on a cloud server, (2) a database that has been outsourced to a third party, or (3) a database running on a machine that could be compromised by insiders or hackers.
There are several challenges for ensuring the authenticity and integrity of databases primarily due to the ability to execute queries over this data—e.g., using SQL—and to make updates to parts of the database. The correctness of query results and validity of updates are crucial requirements for databases. In order to ensure authenticity, it is necessary for the database server to guarantee correctness, completeness and transactional consistency.
Correctness requires that all answers to a given query do indeed come from the authentic database. In other words, this implies that the values returned are not manufactured by the server or corrupted along the communication path.
Completeness requires that all tuples that should be present in a query answer are indeed part of the answer. In other words, the database host has evaluated the query correctly and has returned all tuples that are produced as a result without dropping any out.
Transactional consistency requires that the current consistent state is indeed the correct state corresponding to the initial state followed by the correct application of all previous valid transactions. Query freshness is part of transactional consistency.
Many applications may also require, e.g., due to regulatory compulsions, to keep the provenance of updates to the database. This can be particularly important to check if malicious activity occurred in the past. For purposes of this application, the term “provenance” refers to the order of changes to a database, the exact transactions that made those changes, and the authorization from an accessor that authorized the changes.
Existing solutions assume that the data being outsourced to a third-party are not modified at the outsourcing server. In other words, it is assumed that all updates are authenticated by the data owner and then sent to the database server such that the legitimacy of any data that is part of the outsourced database is established directly by the data owner. In an untrusted database setting (e.g., a cloud database setting), this assumption breaks down. A typical outsourced database usually supports large numbers of authorized clients that run transactions directly on the database. Updates to the data are made through these transactions. It is infeasible for the database owner to determine the correct updates for each transaction. The validity of these modifications made to the database is determined by the standard transactional semantics of databases. Thus, there is a need to assure the database owner that the (untrusted) server is indeed correctly executing all transactions.
In addition to these requirements from the data owner's perspective, there is a requirement from the outsource service provider's perspective. The server should be able to prove its innocence if it has faithfully executed all transactions, for example, indemnity for the server against false claims of malpractice.
Given that the goal of the outsourcing is to alleviate the burden on the data owner, satisfactory solutions need to minimize the overhead and role of the data owner in establishing the authenticity and integrity of the solutions. In this regard, existing solutions are inadequate as they require the data owner to play a significant role. In addition, existing solutions also place significant overhead on the service provider. While this may work for some applications, many outsourced databases are expected to have both a large size and high rate of querying and updates. Thus it is necessary to explore more efficient solutions with low overheads for all involved parties.
Therefore, there is a need for a novel solution to ensure authenticity and integrity of an untrusted database in the presence of transactional updates that runs directly on the untrusted database. There is also a need for an authentication mechanism to ensure correctness, completeness, and transactional consistency, including the assurance to the database owner that the (untrusted) server is indeed correctly executing all transactions. Furthermore, there is a need for providing indemnity of the server against false claims of incorrect operation. In addition, there is a need for implementing the aforementioned checks without excessive demand on the server resources or altering the internal structure of the outsourced database. The invention satisfies these needs. In addition, the invention provides assured provenance for all changes to the data—i.e., using the exact same mechanism for ensuring authenticity and integrity, the invention can provide incontrovertible evidence about all the modifications that have been made to the data.